﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 最长定差子序列
class Solution
{
public:
    int longestSubsequence(vector<int>& arr, int difference)
    {
        // dp[i]:表示以i位置为结尾的所有子序列的最长定差子序列的长度
        // 这里如果前面有相同的数,我们选择最后一个即可，因为dp[j1]<=dp[j2]
        // 这里我们可以使用哈希表进行优化
        unordered_map<int, int> hash; //arr[i] -- dp[i]
        hash[arr[0]] = 1;
        int ret = 1;
        for (int i = 1; i < arr.size(); i++)
        {
            // 如果arr[i]-difference不存在 hash[arr[i]-difference]为0
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }

        return ret;
    }
};


// 最长的斐波那契子序列的长度
class Solution
{
public:
    int lenLongestFibSubseq(vector<int>& arr)
    {
        // dp[i][j]表示以i以及j结尾的斐波那契子序列的长度
        // j在前,i在后
        // x = arr[j] - arr[i] x的下标为k
        // k i j 
        // k < i  dp[i][j] = dp[k][i] + 1
        // i < k < j  dp[i][j] = 2
        // i > j dp[i][j] = 2
        int n = arr.size();
        unordered_map<int, int> hash; // arr[i]---i
        for (int i = 0; i < n; i++)
        {
            hash[arr[i]] = i;
        }
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        // 固定最后⼀个位置
        for (int j = 2; j < n; j++)
        {
            // 固定倒数第⼆个位置
            for (int i = 1; i < j; i++)
            {
                int x = arr[j] - arr[i];
                // if(x < arr[i] && hash.count(x))
                if (hash.count(x) && hash[x] < i)
                    dp[i][j] = dp[hash[x]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }

        return ret < 3 ? 0 : ret;
    }
};

// 最长等差数列
class Solution
{
public:
    int longestArithSeqLength(vector<int>& nums)
    {
        // dp[i][j]表示以i以及j结尾的等差子序列的最长长度
        // a b c  a = 2*b-c
        // k i j 
        // k < i dp[i][j] = dp[k][i] + 1
        // i < k < j dp[i][j] = 2
        // i > j dp[i][j] = 2
        int n = nums.size();
        unordered_map<int, int> hash; // nums[i]--i
        hash[nums[0]] = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        // 固定倒数第二个数
        for (int i = 1; i < n; i++)
        {
            // 固定最后一个数 
            for (int j = i + 1; j < n; j++)
            {
                int x = 2 * nums[i] - nums[j];
                if (hash.count(x))
                {
                    dp[i][j] = dp[hash[x]][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }

        return ret;
    }
};

class Solution
{
public:
    int longestArithSeqLength(vector<int>& nums)
    {
        // dp[i][j]表示以i以及j结尾的等差子序列的最长长度
        // a b c  a = 2*b-c
        // k i j 
        // k < i dp[i][j] = dp[k][i] + 1
        // i < k < j dp[i][j] = 2
        // i > j dp[i][j] = 2
        int n = nums.size();
        unordered_map<int, vector<int>> hash; // x--i,j,k
        for (int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        // 固定最后一个数
        for (int j = 2; j < n; j++)
        {
            // 固定倒数第二个数
            for (int i = 1; i < j; i++)
            {
                int x = 2 * nums[i] - nums[j];
                if (hash.count(x))
                {
                    for (auto a : hash[x])
                    {
                        if (a < i)
                        {
                            dp[i][j] = dp[a][i] + 1;
                            ret = max(ret, dp[i][j]);
                        }
                        else break;
                    }
                }
            }
        }

        return ret;
    }
};


// 等差数列划分2
class Solution
{
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        // dp[i][j]表示以i 以及 j结尾的等差数列的长度
        // a b c 
        // k i j
        // k < i dp[i][j] = dp[k][i] + 1
        // 
        int n = nums.size();
        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);

        vector<vector<int>> dp(n, vector<int>(n));
        int sum = 0;
        for (int j = 2; j < n; j++)
        {
            for (int i = 1; i < j; i++)
            {
                long long x = (long long)2 * nums[i] - nums[j];
                if (hash.count(x))
                {
                    for (auto k : hash[x])
                    {
                        if (k < i)
                            dp[i][j] += dp[k][i] + 1;
                        else break;
                    }
                    sum += dp[i][j];
                }
            }
        }

        return sum;
    }
};
int main()
{
    return 0;
}